package com.example.demo.leetcode100题;

import com.example.demo.StopWatchTemplate;

/**
 * @author：zzc
 * @date: 2022/9/1
 */
public class 反转链表 {

    //给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    //示例 1：
    //输入：head = [1,2,3,4,5]
    //输出：[5,4,3,2,1]
    //示例 2：
    //输入：head = [1,2]
    //输出：[2,1]
    //示例 3：
    //输入：head = []
    //输出：[]

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(4);

        System.out.println(StopWatchTemplate.doSupplier(() -> reverseList(node1)));
    }

    //解法
    //定义指针 pre，cur 分别指向 null 和头节点。
    //
    //遍历链表，将 cur.next 临时保存到 t 中，然后改变指针 cur 指向的节点的指向，将其指向 pre 指针指向的节点，即 cur.next = pre。然后 pre 指针指向 cur，cur 指针往前走。
    //
    //当遍历结束后，返回 pre 指针即可。
    private static ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }

        return pre;
    }
}
